package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:23
 */
public class M5 {
    public static void main(String[] args) {
        System.out.println(new M5().cuttingRope(120));
    }


    //动态规划第一种求法
    public int cuttingRope(int n) {
        if(n == 2) {
            return 1;
        }
        if(n == 3){
            return 2;
        }
        int mod = (int)1e9 + 7;
        long res = 1;
        while(n > 4) {
            res *= 3;
            res %= mod;
            n -= 3;
        }
        return (int)(res * n % mod);
    }


//    //贪心算法
//    public int cuttingRope(int n){
//        if (n <= 3 && n > 0){
//            return n-1;
//        }
//        int timesOf3 = n / 3;//能剪多少段长度为3的绳子
//        if ((n-timesOf3*3)==1){//剩余长度为4
//            timesOf3 -=1;
//        }
//        int timeOf2 = (n-timesOf3*3)/2;//将剩余的剪成两段
//        return (int) ((Math.pow(3,timesOf3)%1000000007)*(Math.pow(2,timeOf2)%1000000007));
//    }
}
